Search results for "Kolmogorov structure function"
showing 4 items of 4 documents
Application of kolmogorov complexity to inductive inference with limited memory
1995
A b s t r a c t . We consider inductive inference with limited memory[l]. We show that there exists a set U of total recursive functions such that U can be learned with linear long-term memory (and no short-term memory); U can be learned with logarithmic long-term memory (and some amount of short-term memory); if U is learned with sublinear long-term memory, then the short-term memory exceeds arbitrary recursive function. Thus an open problem posed by Freivalds, Kinber and Smith[l] is solved. To prove our result, we use Kolmogorov complexity.
Finite State Transducers with Intuition
2010
Finite automata that take advice have been studied from the point of view of what is the amount of advice needed to recognize nonregular languages. It turns out that there can be at least two different types of advice. In this paper we concentrate on cases when the given advice contains zero information about the input word and the language to be recognized. Nonetheless some nonregular languages can be recognized in this way. The help-word is merely a sufficiently long word with nearly maximum Kolmogorov complexity. Moreover, any sufficiently long word with nearly maximum Kolmogorov complexity can serve as a help-word. Finite automata with such help can recognize languages not recognizable …
Effects of Kolmogorov complexity present in inductive inference as well
1997
For all complexity measures in Kolmogorov complexity the effect discovered by P. Martin-Lof holds. For every infinite binary sequence there is a wide gap between the supremum and the infimum of the complexity of initial fragments of the sequence. It is assumed that that this inevitable gap is characteristic of Kolmogorov complexity, and it is caused by the highly abstract nature of the unrestricted Kolmogorov complexity.
Kolmogorov Superposition Theorem and Its Application to Multivariate Function Decompositions and Image Representation
2008
International audience; In this paper, we present the problem of multivariate function decompositions into sums and compositions of monovariate functions. We recall that such a decomposition exists in the Kolmogorov's superposition theorem, and we present two of the most recent constructive algorithms of these monovariate functions. We first present the algorithm proposed by Sprecher, then the algorithm proposed by Igelnik, and we present several results of decomposition for gray level images. Our goal is to adapt and apply the superposition theorem to image processing, i.e. to decompose an image into simpler functions using Kolmogorov superpositions. We synthetise our observations, before …